力扣90——子集 II

这道题主要就是利用递归,优化的时候需要利用数据结构的特性。

原题

给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

原题url:https://leetcode-cn.com/problems/subsets-ii/

解题

递归

这道题,针对已经刷了不少题目的我们而言,应该第一想到的就是递归了,从第1个数开始,每次遍历1个数,如果和之前的数相同则跳过,然后以下一个数为起点,继续遍历。让我们来看看代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
// 从小到大排序
Arrays.sort(nums);
// 最终结果
List<List<Integer>> result = new LinkedList<>();
result.add(new LinkedList<>());
// 回溯
dfs(0, nums, new Stack<>(), result);

return result;
}

public void dfs(int index, int[] nums, Stack<Integer> stack, List<List<Integer>> result) {
if (index >= nums.length) {
return;
}

for (int i = index; i < nums.length; i++) {
// 在这一次总的查找中,如果当前节点和上一个节点相同,则跳过
if (i > index && nums[i] == nums[i - 1]) {
continue;
}
// 添加该数
stack.push(nums[i]);
// 作为一种情况,放进结果中
result.add(new LinkedList<>(stack));
// 继续回溯
dfs(i + 1, nums, stack, result);
// 回退
stack.pop();
}
}
}

提交OK,执行用时:2 ms,内存消耗:36.5 MB,但执行用时只战胜40.16%,那就来优化一下。

优化

看了第一眼,我真的不知道该如何优化。我先是想到将递归改成迭代,但感觉并没有从时间上做出优化,不过还是给大家看一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
if (nums == null || nums.length == 0) {
return new LinkedList<>();
}

// 从小到大排序
Arrays.sort(nums);
// 最终结果
List<List<Integer>> result = new ArrayList<>(1 << nums.length);
result.add(0, new LinkedList<>());
// 上一步新解的开始下标
int newStartIndex = 1;
// 遍历添加
for (int i = 0; i < nums.length; i++) {

int j = 0;
// 和上一个数字相同,则只针对上一步的新解增加
if (i > 0 && nums[i] == nums[i - 1]) {
j = newStartIndex;
}
int length = result.size();
newStartIndex = length;
for (;j < length; j++) {
List<Integer> tempList = result.get(j);
List<Integer> newList = new LinkedList<>(tempList);
newList.add(nums[i]);
result.add(newList);
}
}

return result;
}
}

提交之后,果然不出所料,和之前一样,那就再让我们想想。

还记得在之前文章中曾经说过,new LinkedList<>(Collection<? extends E> c)其内部依旧是遍历,很耗性能。因此我专门看了一下new ArrayList<>(Collection<? extends E> c),其内部最终会调用Systemp.arraycopy。让我们再试一次:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
// 从小到大排序
Arrays.sort(nums);
// 最终结果
List<List<Integer>> result = new LinkedList<>();
result.add(new ArrayList<>());
// 回溯
dfs(0, nums, new Stack<>(), result);

return result;
}

public void dfs(int index, int[] nums, Stack<Integer> stack, List<List<Integer>> result) {
if (index >= nums.length) {
return;
}

for (int i = index; i < nums.length; i++) {
// 在这一次总的查找中,如果当前节点和上一个节点相同,则跳过
if (i > index && nums[i] == nums[i - 1]) {
continue;
}
// 添加该数
stack.push(nums[i]);
// 作为一种情况,放进结果中
result.add(new ArrayList<>(stack));
// 继续回溯
dfs(i + 1, nums, stack, result);
// 回退
stack.pop();
}
}
}

提交之后,果然OK了,执行用时:1 ms,战胜100%的 java 提交记录。

我这里再说明一下,LinkedList 的遍历拷贝,每个元素都需要重新计算内存位置,而 ArrayList 的拷贝,可以直接一次性申请一大片空间,写入和遍历的速度会更快。

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题目只要利用递归就可以解决了,但优化的时候,需要注意数据结构(是不是我之前用一些的 LinkedList 换成 ArrayList 会效果更好呢)。

有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。

https://death00.github.io/

公众号:健程之道

健健 wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
如果您感觉文章不错,也愿意支持一下作者的话